
#include <iostream>
#include <stack>
#include <string>
#include <algorithm>

bool isOpening(char ch) {
    return ch == '(' || ch == '[' || ch == '{' || ch == '<';
}

bool matches(char opening, char closing) {
    return (opening == '(' && closing == ')') ||
           (opening == '[' && closing == ']') ||
           (opening == '{' && closing == '}') ||
           (opening == '<' && closing == '>');
}

bool isValidSequence(const std::string& s) {
    std::stack<char> stack;
    for (char ch : s) {
        if (isOpening(ch)) {
            stack.push(ch);
        } else {
            if (stack.empty() || !matches(stack.top(), ch)) {
                return false;
            }
            stack.pop();
        }
    }
    return stack.empty();
}

std::string removeSpaces(std::string str) {
    str.erase(std::remove(str.begin(), str.end(), ' '), str.end());
    return str;
}

int main() {
    std::cout << "Enter sequence:";
    std::string sequence;
    std::getline(std::cin, sequence);

    sequence = removeSpaces(sequence);

    std::cout << (isValidSequence(sequence) ? "True" : "False") << std::endl;

    return 0;
}
